package com.nowcoder.code.lcof;

public class JZ12 {

    public static void main(String[] args) {
        char[][] matrix = {{'a', 'b', 'c', 'e'}, {'s', 'f', 'c', 's'}, {'a', 'd', 'e', 'e'}};
        JZ12 jz12 = new JZ12();
        System.out.println(jz12.hasPath(matrix, "bcced"));
        System.out.println(jz12.hasPath(matrix, "abcd"));
    }

    char[][] matrix;
    char[] cw;

    public boolean hasPath(char[][] matrix, String word) {
        this.matrix = matrix;
        cw = word.toCharArray();

        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (cw[0] == matrix[i][j]) {
                    if (recursion(i, j, 0)) {
                        return true;
                    }
                }
            }
        }

        return false;
    }

    public boolean recursion(int i, int j, int l) {
        if (l == cw.length) {
            return true;
        }
        if (i >= matrix.length || i < 0 || j >= matrix[0].length || j < 0) {
            return false;
        }
        if (matrix[i][j] != cw[l]) {
            return false;
        }
        matrix[i][j] = '.';
        boolean b = recursion(i - 1, j, l + 1) ||
                recursion(i + 1, j, l + 1) ||
                recursion(i, j + 1, l + 1) ||
                recursion(i, j - 1, l + 1);

        if (b) {
            return true;
        }
        matrix[i][j] = cw[l];

        return false;
    }


}
